CF113D Museum

$f_{i,j}$：两人分别在房间 $i,j$ 的概率。初始状态 $f_{a,b}=1$

$f_{i,j}=p_ip_jf_{i,j}+\sum_{(i,u) \in E}\sum_{(j,v) \in E} \frac{1-p_u}{\deg_u} \frac{1-p_v}{\deg_v}f_{u,v}$

$+\sum_{(i,u) \in E} \frac{1-p_u}{\deg_u} p_jf_{u,j}+\sum_{(j,v) \in E} p_i\frac{1-p_v}{\deg_v} f_{i,v}$

注意当后继状态的 $u=v$ 相等时不能转移。房间 $i$ 相遇的概率即为 $f_{i,i}$。

直接高斯消元即可,时间复杂度 $\mathcal O(n^6)$ 。

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define eps 1e-8

template<typename _T>
void Read( _T &x ) {
	x = 0; char s = getchar();
	for( ; s < '0' || s > '9' ; s = getchar() );
	for( ; s >= '0' && s <= '9' ; s = getchar() ) x = x * 10 + s - '0';
}
template<typename _T>
void Write( _T x ) {
	if( x >= 10 ) Write( x / 10 );
	putchar( x % 10 + '0' ); 
}

const int MAXN = 22;
int n , m , w , deg[ MAXN + 5 ]; double p[ MAXN + 5 ];
bool Graph[ MAXN + 5 ][ MAXN + 5 ];

double a[ MAXN * MAXN + 5 ][ MAXN * MAXN + 5 ];

int hs( int x , int y ) { return ( x - 1 ) * n + y; }
void print( ) {
	printf("------");
	for( int i = 1 ; i <= w ; i ++ )
		for( int j = 1 ; j <= w + 1 ; j ++ )
			printf("%.2f%c", a[ i ][ j ] , j == w + 1 ? '\n' : ' ' );
	printf("--------");
}

void Gauss( ) {
	for( int i = 1 ; i <= w ; i ++ ) {
		int pos = i;
		for( int j = i + 1 ; j <= w ; j ++ )
			if( fabs( a[ j ][ i ] ) > fabs( a[ pos ][ i ] ) ) pos = j;
		swap( a[ pos ] , a[ i ] );
		if( fabs( a[ i ][ i ] ) < eps ) continue;
		for( int j = 1 ; j <= w ; j ++ )
			if( i != j ) {
				double d = a[ j ][ i ] / a[ i ][ i ];
				for( int k = i ; k <= w + 1 ; k ++ )
					a[ j ][ k ] -= a[ i ][ k ] * d;
			}
	}
	for( int i = 1 ; i <= w ; i ++ ) a[ i ][ m + 1 ] /= a[ i ][ i ];
}

int x , y;
int main( ) {
	scanf("%d %d %d %d",&n,&m,&x,&y);
	for( int i = 1 , u , v ; i <= m ; i ++ ) {
		scanf("%d %d",&u,&v); deg[ u ] ++ , deg[ v ] ++;
		Graph[ u ][ v ] = Graph[ v ][ u ] = 1;
	}
	for( int i = 1 ; i <= n ; i ++ ) scanf("%lf",&p[ i ]);
	
	w = n * n;
	a[ hs( x , y ) ][ w + 1 ] = 1;
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ ) {
			a[ hs( i , j ) ][ hs( i , j ) ] = 1 - ( i == j ? 0 : p[ i ] * p[ j ] ); 
			for( int u = 1 ; u <= n ; u ++ )
				for( int v = 1 ; v <= n ; v ++ )
					if( u != v && Graph[ i ][ u ] && Graph[ j ][ v ] )
						a[ hs( i , j ) ][ hs( u , v ) ] = - ( 1 - p[ u ] ) / deg[ u ] * ( 1 - p[ v ] ) / deg[ v ]; 
			for( int u = 1 ; u <= n ; u ++ )
				if( u != j && Graph[ i ][ u ] )
					a[ hs( i , j ) ][ hs( u , j ) ] = - ( 1 - p[ u ] ) / deg[ u ] * p[ j ]; 
			for( int v = 1 ; v <= n ; v ++ )
				if( i != v && Graph[ j ][ v ] )
					a[ hs( i , j ) ][ hs( i , v ) ] = - p[ i ] * ( 1 - p[ v ] ) / deg[ v ]; 
		}
	
	Gauss();
	for( int i = 1 ; i <= n ; i ++ ) printf("%.9f\n", a[ hs( i , i ) ][ w + 1 ] );
	return 0;
}